#include <stdio.h>
#include <stdlib.h>

/*
 * 链式队列. 优点：动态变长，没有最大容量限制，取数据元素相对方便
 * 
 * 不存在伪溢出的问题，长度没有限制，但是插入和删除节点的时间代价较高(动态分配空间)
 */


/*

顺序队列与链式队列 
    链式队列与线性表的单链表相似只不过链式队列只允许从头部进行删除、尾部进行插入.需要为链式队列
	
    创建一个头结点包括两个指针,指向队头的指针(front) 与指向队尾的指针(rear).当两个指针相等时队列为空


	循环队的入队算法如下：
	　　
	1、tail=tail+1； 　　
	2、若tail=n+1，则tail=1； 　　
	3、若head=tail尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理； 　　
	4、否则，Q(tail)=X，结束（X为新入出元素）。 　　
　
	注意：
	（1）有时候队列中还会设置表头结点，就是在对头的前面还有一个结点，这个结点的数据域为空，
			但是指针域指向对头元素。 
	（2）另外，上面的计算还可以利用下面给出的公式cq.rear=(cq.front+1)/max; 　　
			当有表头结点时，公式变为cq.rear=(cq.front+1)/（max+1）。

	队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，
	而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。
 */

struct node
{
  int data;
  struct node * next;
};

struct queue
{
  struct  node * front;
  struct  node * rear;
};

void init(struct queue * queue)
{
  queue->front = queue->rear = NULL;
}

void enqueue(struct queue * queue, int value)
{
  struct node * des;

  des = (struct node *) malloc (sizeof(struct node));
  if (!des) {
    printf("enqueue malloc fail.\n");
    exit(-1);
  }

  des->data = value;
  des->next = NULL; // 队列只能从队尾插入所以下一个结点初始化为NULL

  if (queue->rear == NULL)
    queue->front = queue->rear = des;
  /*else // 可用这一句搞定。为添加注释，故改为两行
    queue->rear = queue->rear->next = des; */
  else {
    queue->rear->next = des;// 将队尾结点的指针指向新结点,如果新结点为第一个结点则q->rear->next相当于q->front->next 
    queue->rear = des;// 将指向队尾的指针指向新结点 
  }
}

void dequeue(struct queue * queue)
{
  struct node * des;
  int temp;

  if (queue->front == NULL) {
    printf("queue is empty, diable dequeue.\n");
    exit(-1);
  }

  des = queue->front;
  //queue->front = des->next;
  queue->front = queue->front->next;
  if (queue->front == NULL)
    queue->rear = NULL;
  free(des);
}

int peekqueue(struct queue * queue)
{
  if (queue->front == NULL) {
    printf("queue is empty.\n");
    return 0;
  }

  return queue->front->data;
}

int empty(struct queue * queue)
{
  if (queue->front == NULL)
    return 1;
  else
    return 0;
}

int get(struct queue * src)
{
  if (empty(src)) {
    printf("queue is empty.\n");
    return 0;
  }
  
  return src->front->data;
}

void clear(struct queue * queue)
{
  struct node * des;

  des = queue->front;
  while (des != NULL) {
    queue->front = queue->front->next;
    free(des);
    des = queue->front;
  }

  queue->rear = NULL;
}

int length(struct queue * src)
{
  struct node * des;
  int len;

  des = src->front;
  len = 1;
  while (des != src->rear) {
    len++;
    des = des->next;
  }

  return len;
}

void display(struct queue * src)
{
  struct node * des;

  if (src->front == src->rear)
    return ;

  des = src->front;
  while (des != src->rear) {
    printf(" %d ", des->data);
    des = des->next;
  }
  printf(" %d ", des->data);
  printf("\nqueue length = %d\n\n", length(src));
}

int main()
{
  struct queue queue;
  int i;
  
  init(& queue);
  for(i = 1; i <= 10; i++) 
    enqueue(& queue, i);

  display(& queue);		// 1  2  3  4  5  6  7  8  9  10 
  enqueue(& queue, 11);
  display(& queue);		// 1  2  3  4  5  6  7  8  9  10  11
  
  dequeue(& queue);		// del 1
  dequeue(& queue);		// del 2
  dequeue(& queue);		// del 3
  dequeue(& queue);		// del 4
  dequeue(& queue);		// del 5
  display(& queue);		//  6  7  8  9  10  11

  enqueue(& queue, 55);
  enqueue(& queue, 66);
  enqueue(& queue, 75);
  enqueue(& queue, 76);
  enqueue(& queue, 85);
  enqueue(& queue, 86);
  display(& queue);		// 6  7  8  9  10  11  55  66  75  76  85  86

  /*
  while(queue.front != NULL) {
    printf(" %d ", get(&queue));
    dequeue(& queue);
    }*/
  clear(& queue);
}
